package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-06-06 18:36
 */
public class 题库_0079_单词搜索 {

  static
  class Solution {

    private static final int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean exist(char[][] board, String word) {
      char[] words = word.toCharArray();
      boolean[][] mark = new boolean[board.length][board[0].length];
      for (int i = 0; i < board.length; ++i) {
        for (int j = 0; j < board[0].length; ++j) {
          if (board[i][j] == words[0]) {
            mark[i][j] = true;
            if (helper(board, i, j, 1, mark, words)) {
              return true;
            }
            mark[i][j] = false;
          }
        }
      }
      return false;
    }

    private boolean helper(char[][] board, int i, int j, int index, boolean[][] mark, char[] words) {
      if (index == words.length) {
        return true;
      }

      for (int k = 0; k < next.length; ++k) {
        int nextI = i + next[k][0];
        int nextJ = j + next[k][1];
        if (isValidPoint(nextI, nextJ, board.length, board[0].length) && !mark[nextI][nextJ] && board[nextI][nextJ] == words[index]) {
          mark[nextI][nextJ] = true;
          if (helper(board, nextI, nextJ, index + 1, mark, words)) {
            return true;
          }
          mark[nextI][nextJ] = false;
        }
      }

      return false;
    }

    private boolean isValidPoint(int i, int j, int m, int n) {
      return i >= 0 && i < m && j >= 0 && j < n;
    }

  }

}
